package com.daybyday.day1.day7;

import com.interview.javabasic.JUC.A;
import org.omg.PortableInterceptor.INACTIVE;

import javax.swing.*;
import java.util.*;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2021/1/5

*/
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
    Node(int v){
        this.val = v;
    }
    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
}

public class Solution {
    Node res = new Node(-1);

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.hammingWeight(000000000000001011));
        System.out.println(Integer.toBinaryString(3));
        System.out.println(Integer.toBinaryString(9));
        System.out.println(Integer.toBinaryString(27));
        System.out.println(Integer.toBinaryString(81));
        String str = "22213";
        String[] split = str.split("/+");
        System.out.println(split[0]);
    }

    public int hammingWeight(int n) {

        int length = n + "".length();
        int res = 0;
        for(int i = 0 ; i < length; i++){
            if((n & (1 << i)) == 1){
                res++;
            }
        }
        return res;
    }

    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3 ; int b = n % 3;
        int tmp = 1000000007;
        int res = 1;
        for(int i = 0; i < a - 1;i ++){
            res = 3 * res % tmp;
        }
        if(b == 0) return (int) res * 3 % tmp;
        if(b == 1) return (int)res * 4  %tmp;
        return (int)res * 3 * 2 % tmp;
    }


    public int movingCount(int m, int n, int k) {
        int count = 0;
        boolean[][] reach = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        count ++ ;
        reach[0][0] = true;
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int new_m = poll[0];int new_n = poll[1];
            if (new_m + 1 < m && new_n < n && getPosSum(new_m + 1) + getPosSum(new_n) <= k){
                if (!reach[new_m + 1][new_n]){
                    queue.add(new int[]{new_m + 1,new_n});
                    reach[new_m + 1][new_n] = true;
                    count++;
                }
            }
            if (new_m  < m && new_n + 1 < n && getPosSum(new_m) + getPosSum(new_n + 1) <= k){
                if (!reach[new_m][new_n + 1]){
                    queue.add(new int[]{new_m,new_n + 1});
                    reach[new_m][new_n + 1] = true;
                    count++;
                }
            }
        }
        return count;
    }

    public int getPosSum(int x){
        return x / 10 + x % 10;
    }


   int min = Integer.MAX_VALUE;

    public int numSplits(String s) {
        int count = 0;
        int n = s.length();
        boolean[] leftChar = new boolean[26];
        boolean[] rightChar = new boolean[26];
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 1;
        right[n - 1] = 1;
        leftChar[s.charAt(0) - 'a'] = true;
        rightChar[s.charAt(n - 1) - 'a'] = true;
        for(int i = 1; i< n; i++){
            if(leftChar[s.charAt(i) - 'a']){
                left[i] = left[i - 1];
            }else{
                left[i] = left[i - 1] + 1;
                leftChar[s.charAt(i) - 'a'] = true;
            }
        }

        for(int i = n-2; i>= 0; i--){
            if(rightChar[s.charAt(i) - 'a']){
                right[i] = right[i + 1];
            }else{
                right[i] = right[i + 1] + 1;
                rightChar[s.charAt(i) - 'a'] = true;
            }
        }
        for(int i = 0 ; i < n; i++){
            if(left[i] == right[i+1]){
                count++;
            }
        }
        return count;
    }

    public int stringToInt(String s){
        int num = 0;
        for (char c : s.toCharArray()) {
            num |= 1 << c - 'a';
        }

        return Integer.bitCount(num);
    }

    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
         dfs(nums,0,sum);
        return 0;
    }

    public int dfs(int[] nums,int i,int sum){
        if (i >=nums.length) return 0;
        sum += nums[i];
        return  dfs(nums,i+1,sum);

    }

    public List<Integer> partitionLabels(String S) {
        int i = 0;
        int start = 0,end = 0;
        List<Integer> res = new ArrayList<>();
        while (i < S.length()){
            char c = S.charAt(i);
            start = i ;
            int j = S.lastIndexOf(S.charAt(i));
            end = j;
            for (int k = i + 1; k <= end; k++) {
                end = S.lastIndexOf(S.charAt(k)) > end ? S.lastIndexOf(S.charAt(k)) :end;
            }
            res.add(end - start + 1);
            i = end + 1;
        }
        return res;
    }

    public boolean canConvertString(String s, String t, int k) {
        int i = 0 ;
        int[] count = new int[26];
        List<Integer> list = new ArrayList<>();
        while(i < s.length()){
            int tmp = t.charAt(i) - s.charAt(i) >= 0 ?  t.charAt(i) - s.charAt(i):26 + t.charAt(i) - s.charAt(i);
            count[tmp]++;
            i++;
        }

        for(int m = 1; m < count.length; m++){
            if(count[m] != 0){
                for(int j = 0; j < count[m]; j++){
                    int tmp = m + j * 26;
                    if(list.contains(tmp)){
                        list.add(tmp + 26);
                        continue;
                    }
                    list.add(tmp);
                }
            }
        }
        return list.get(list.size()-1) > k ? false : true;

    }

    public int magicalString(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        int[] magic = new int[n];
        int[] magic2 = new int[n];
        magic[0] = magic2[0] = 1;
        magic[1] = 2;
        int count = 1;
        int i = 2;
        int j = 1;
        while ( j < n){
            if ((magic2[j - 1] & 1) == 0){
                for (int k = 0; k < magic[i-1] & j < n; k++) {
                    magic2[j] = magic[j] = 1;
                    count++;
                    j++;
                }
            }else{
                for (int k = 0; k < magic[i-1] && j < n ; k++) {
                    magic2[j] = magic[j] = 2;
                    j++;
                }
            }
            i++;
        }
        return count;
    }

    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int row = grid.length;
        int colum = grid[0].length;
        int[][] dp = new int[row][colum];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < colum; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < colum; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[row - 1][colum - 1];
    }

    List<Integer> list = new ArrayList<>();
    public void dfs1(int i,int j ,int[][] grid,int cur){
        if (i == grid.length || j == grid[0].length){
            return;
        }
        cur += grid[i][j];
        if (i == grid.length - 1 && j == grid[0].length - 1){
            min = min < cur ? min : cur;
            return;
        }

        dfs1(i+1,j,grid,cur);
        dfs1(i,j+1,grid,cur);
    }

    public void dfs2(int i,int j ,int[][] grid,int cur){
        cur += grid[i][j];
        if (i == grid.length - 1 && j == grid[0].length - 1){
            min = min < cur ? min : cur;
            return;
        }
        if (j < grid[0].length - 1 ){
            dfs2(i,j+1,grid,cur);
            if (i < grid.length - 1){
                dfs2(i+1,j,grid,cur);
            }
        }else if (i < grid.length - 1){
            dfs2(i+1,j,grid,cur);
            return;
        }
    }


    public List<String> ambiguousCoordinates(String S) {
        String replace = S.replace("(", "").replace(")", "");
        int i = 1;
        Set<String> res = new HashSet<>();
        StringBuilder sb = new StringBuilder(replace);

        while (i < replace.length()){
            List<String> list = canSplitNumber(sb.substring(0, i));
            List<String> list1 = canSplitNumber(sb.substring(i, sb.length()));
            if (list.size() != 0 && list1.size() != 0){
                for (String s : list) {
                    for (String s1 : list1) {
                        res.add("(" + s + ", " + s1 + ")");
                    }
                }
            }
            i++;
        }
        return new ArrayList<>(res);
    }

    public List<String> getAllPossible(StringBuilder sb){
        List<String> res = new ArrayList<>();
        if (sb.length() == 1) res.add(sb.toString());
        for (int i = 0; i < sb.length() -  1 ; i++) {
            res.add(sb.substring(0,i+1)+"."+sb.substring(i + 1,sb.length()));
        }
        return res;
    }

    public List<String> canSplitNumber(String s){
        List<String> res = new ArrayList<>();
        if (s.length() == 1){
            res.add(s);
            return res;
        }

        if (s.startsWith("0") && s.endsWith("0")){
            return res;
        }
        if (s.startsWith("0")){
            res.add(s.substring(0,1)+"."+s.substring(1,s.length()));
            return res;
        }
        if (s.endsWith("0")){
            res.add(s);
            return res;
        }
        else{
            res = getAllPossible(new StringBuilder(s));
            res.add(s);
            return res;
        }
    }

    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer,Integer> map = new LinkedHashMap<>();
        int res = 0;

        for (List<Integer> list : wall) {
            for (int i = 0; i < list.size() - 1; i++) {
                res += list.get(i);
                if (map.keySet().contains(res)){
                    map.put(res,map.get(res) + 1);
                }else{
                    map.put(res,1);
                }
            }
            res = 0;
        }
        int max = 0;
        for (Integer value : map.values()) {
            System.out.println(value);
            max = max < value && value < wall.size() ? value : max;
        }

        return wall.size() - max;
    }

    public Node flatten(Node head){
        if(head == null) return head;
        Node pseudoHead = new Node(0,null,head,null);

        flattenDFS(pseudoHead,head);

        pseudoHead.next.prev = null;
        return pseudoHead.next;

    }

    public Node flattenDFS(Node prev,Node curr){
        if(curr == null) return prev;
        curr.prev = prev;
        prev.next = curr;

        Node tempNext = curr.next;

        Node tail = flattenDFS(curr,curr.child);
        curr.child = null;
        return flattenDFS(tail,tempNext);
    }

    public void flatterncycle(Node head){
        if (head == null) return;
        res.next = new Node(head.val);
        res = res.next;
        res.next = null;
        res.child = null;
        if (head.child != null) {
            flatterncycle(head.child);
        }
        flatterncycle(head.next);
    }


    public int numberOfSubarrays(int[] nums, int k) {
        List<Integer> begin = new ArrayList<>();
        List<Integer> end = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & 1) == 1 && count == 0){
                count ++;
                begin.add(i);
            }
            if ((nums[i]&1) == 1 && count == k){
                end.add(i);
                count = 0;
            }
        }
        return 0;
    }

    public int findTheLongestSubstring(String s) {
        int n = s.length();
        int[] pos = new int[1 << 5];
        Arrays.fill(pos, -1);
        int ans = 0, status = 0;
        pos[0] = 0;
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == 'a') {
                status ^= (1 << 0);
            } else if (ch == 'e') {
                status ^= (1 << 1);
            } else if (ch == 'i') {
                status ^= (1 << 2);
            } else if (ch == 'o') {
                status ^= (1 << 3);
            } else if (ch == 'u') {
                status ^= (1 << 4);
            }
            if (pos[status] >= 0) {
                ans = Math.max(ans, i + 1 - pos[status]);
            } else {
                pos[status] = i + 1;
            }
        }
        for (int po : pos) {
            System.out.print(po + " ");
        }
        return ans;
    }
}
